package 动态规划.另类的;
import java.util.List;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
public class leetcode131分割字符串dp {
	
		public static List<List<String>> solution(String s){
			List<List<String>> ans= new ArrayList<>();
			LinkedList<String> path =new LinkedList<>();
			if(s==null ||s.length()==0) {
				return ans;
			}
			/*
			 * 要明白 这个 二维表的 含义 
			 * dp[start][end] 表示的是 在 s 中 从start 到为 end位置的 子串是 不是 回文串
			 * 1 代表是回文串
			 * -1不是
			 * 0 表示 还不知道
			 * 用记忆化 搜索 来写 但改不成 最终版本的  动态规划 
			 * 重复的 过程 在于 多次重复的  判断的  回文串   
			 */
			int dp[][] =new int[s.length()][s.length()];
			process(0,s,ans,path,dp);
			return ans;
		}
		// 记忆化搜索 
		//这些 参数 其实 都可以 直接 声明称全局变量 但是 空间复杂度 会不会降低呢 这个 还需要测试一下 最终结果
		public static void process(int index,String s,List<List<String>> ans,LinkedList<String>
		path,int dp[][]) {
			if(index == s.length()) {
				ans.add(new LinkedList<>(path));
				return ;
			}
			for(int i = index; i < s.length(); i++) {
				if(dp[index][i] == -1) {
//					continue;
//					  直接 return 呗 说明当前分支 从该层 就已经断了 那就回到 上一层 从新 规划 
					return ;
				}
				if(dp[index][i] == 1 || isPalindrome(s,index,i,dp)) {
					path.add(s.substring(index, i+1));
					// 这里是 i+1 不是index +1; 细节问题 要注意 不然后面 debug 很难受 
					process(i+1,s,ans,path,dp);
					path.removeLast();
				}
				
			}
			
		}
		public static boolean isPalindrome(String s,int start,int end,int dp[][]) {
			char arr[]= s.toCharArray();
			for(int i=start,j=end; i< j ;i++,j--) {
				if(arr[i] != arr[j]) {
					dp[start][end]=-1;
					return false;
				}
			}
			dp[start][end]=1;
			return true;
		}
/**
 * 
 * 第二次 写 
 * 明显 感觉这种 暴力 递归 是  有 重复过程的对吧
 * 举个例子：
 * aabb
 * 递归 中  会有 四层 for循环
 * 1 层： a , aa ,aab ,aabb
 * 2 层： a ,ab , abb 
 * 3层 :  b ,bb
 * 4 层 : b
 * 递归 是从下 向上 进行返回的 
 */
	public static List<List<String>>  solutionTwo(String s){
		List<List<String>> ans  = new ArrayList<>();
		Deque<String> path = new ArrayDeque<>();
		backTracing(ans,path,0,s);
		return ans;
	}
		
	public static  void backTracing(List<List<String>> ans,Deque<String> path,int index,String s) { 	
		if(index == s.length()) {
			ans.add(new ArrayList<>(path));
			return ;
		}
/**
 * 这里 我感觉  写  i = index +1 递归放入 时候 传 i 
 * 可以 但没必要 这样做
 */
		for(int i = index;i < s.length(); i++) {
			if(!judge(s.toCharArray(),index,i)) {
				return ;
//				 break;
			}
			path.addLast(s.substring(index, i+1));
			backTracing(ans,path,i+1,s);
			path.removeLast();
		}
	}
	public static boolean judge(char [] s,int start,int end) {
		for(int i = start,j = end; i < j;i++,j--) {
			    if(s[i] != s[j]) {
//			    	dp[start][end] = -1;
			    	return false;
			    }
		}
//		dp[start][end] = 1;
		return true;
	}
	public static void judge(char [] s,int start,int end,int dp[][]) {
		for(int i = start,j = end; i < j;i++,j--) {
			    if(s[i] != s[j]) {
			    	dp[start][end] = -1;
			    	return ;
//			    	return false;
			    }
		}
		dp[start][end] = 1;
//		return ;
//		return true;
	}
/**
 * 	下面 用记忆化  搜索 来写 
 * 这道题 的 这里的 优化 仅仅 是  记忆化 搜索的 优化 跟        动态 规划    并     没 有 太大关系
 * 就是单纯的 把 已经 计算过的 子过程 给 存起来 下次 直接用 而不用 在计算 了  
 */
public static List<List<String>>solutionMemorySearch(String s) {
	List<List<String>> ans  = new ArrayList<>();
	Deque<String> path = new ArrayDeque<>();
	int len = s.length();
	/**
	 * 虽然 起名字 是 dp  但 这个跟动态规划 没有关系 只是一个缓存表而已
	 * 这里 不用 初始化 为    -1  
	 * 假如 不是 回文串 直接 填值 -1 
	 * 是 就填值 为 1 这不就行了
	 */
	int dp[][] = new int [len][len];
	backTracing(ans,path,0,s,dp);
	return ans;
	
}
public static  void backTracing(List<List<String>> ans,Deque<String> path,int index,String s,int dp[][]) {
		if(index == s.length()) {
			ans.add(new ArrayList<>(path));
			return ;
		}
		for(int i = index ; i < s.length(); i++) {
/**
* 如果 要这样 构建 这个 分支 逻辑的  话  那 judge      函数 都不用 返回 Boolean 值 对吧 
* 都用不到 对吧
			 */
			if(dp[index][i] == 0) {
				judge(s.toCharArray(),index,i,dp);
			}
			/**
			 *  下面 肯定是错的 怎么   会是 return
			 */
			if(dp[index][i] == -1) {
				continue ;
			}
//			if(dp[index][i] != 1) {
//				judge(s.toCharArray(),index,i,dp);
//			}
			path.addLast(s.substring(index,i+1));
			backTracing(ans,path,i+1,s,dp);
			path.removeLast();
		}
	}

	
	
	
	
	public static void main(String []args) {
		String str = "aab";
		System.out.println(solution(str));
		System.out.println(solutionTwo(str));
		System.out.println(solutionMemorySearch(str));
//	System.out.println();
	}
}
